package com.top145;

//https://leetcode.cn/problems/count-primes/solutions/507461/javadai-ma-liang-chong-jie-jue-fang-shi-by-sdwwld/?envType=featured-list&envId=2ckc81c%3FenvType%3Dfeatured-list&envId=2ckc81c
public class Solution204 {
    public int countPrimes(int n) {
        boolean[] isPrimes = new boolean[n];
        int count = 0;
        for (int i = 2; i < n; i++) {
            if (isPrimes[i]) continue;
            count++;
            for (int j = i; j < n; j += i) {
                isPrimes[j] = true;
            }
        }
        return count;
    }
}
